package main.sort;

public class ShellSort extends BaseSort {

    public ShellSort(int[] array) {
        super(array);
        this.name = "希尔排序";
    }

    /**
     * 根据某一增量分为若干小数组，并对小数组分别进行插入排序。
     * 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序
     * <br>
     * [8, 7, 6, 5, 4, 3, 2, 1]<br>
     * [4, 3, 2, 1, 8, 7, 6, 5]<br>
     * [1, 2, 3, 4, 5, 6, 7, 8]
     */

    @Override
    public void sort() {
        int len = array.length;
        int gap = 1;
        while (len > gap) {
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                int temp = array[i];
                int j = i - gap;
                while (j >= 0 && array[j] > temp) {
                    array[j + gap] = array[j];
                    j -= gap;
                }
                array[j + gap] = temp;
            }
            gap /= 3;
            print();
        }
    }
}
